package com.cy3;

/**
 * @author CY
 * @date 2022/10/11 05:07
 **/
public class MySingleList {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;

    public void creatList() {
        ListNode listNode1 = new ListNode(45);
        ListNode listNode2 = new ListNode(78);
        ListNode listNode3 = new ListNode(25);
        ListNode listNode4 = new ListNode(34);
        ListNode listNode5 = new ListNode(116);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;
    }

    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    public void display(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int val) {
        ListNode listNode = new ListNode(val);
        listNode.next = this.head;
        head = listNode;
    }

    //尾插法
    public void addLast(int val) {
        ListNode listNode = new ListNode(val);
        ListNode cur = this.head;
        if (this.head == null) {
            this.head = listNode;
        } else {
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = listNode;
        }
    }

    //任意位置插入（合法）插入单链表节点的时候，注意分三种情况，头插，尾插，和一般的插入，一般的插入又分为几个步骤（找前驱（移动pos-1次），再绑定靠后的部分！）
    public void addIndex(int pos, int val) {
        if (pos < 0 || pos > this.size()) {
            throw new IllegalArgumentException("Invalid index");
        }
        if (pos == 0) {
            this.addFirst(val);
            return;
        }
        if (pos == size()) {
            this.addLast(val);
            return;
        }
        ListNode listNode = new ListNode(val);
        ListNode cur = this.head;
        int m = pos - 1;
        while (m > 0) {
            cur = cur.next;
            m--;
        }
        listNode.next = cur.next;
        cur.next = listNode;
        return;
    }

    //删除单链表时注意单独删除头节点的情况；一般情况找前驱
    public void remove(int key) {
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
        System.out.println("找不到该节点！");
    }
    //

    public void removeAllKey(int key) {
        if (this.head == null) {
            return;
        }
        //头尾指针
        ListNode prev = head;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        //一定注意这里的头节点放在最后删除
        if (head.val == key) {
            head = head.next;
        }
    }

    //翻转链表
    public ListNode reverseList() {
        //自己第一次的想法,也能实现，但是太挫
//        if (head == null) {
//            return null;
//        }
//        ListNode cur = head;
//        while (cur.next.next != null) {
//            cur = cur.next;
//        }
//        MySingleList rs = new MySingleList();
//        while (head != null) {
//            rs.addFirst(head.val);
//            head = head.next;
//        }
//        return rs.head;
        //正规写法
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        //1.定义cur，来遍历该单链表
        ListNode cur = head.next;
        //2.将头节点置空
        head.next = null;
        while (cur != null) {
            //记录下一个位置
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;

    }

    //链表中间元素
    public ListNode middleNode() {
        ListNode fast = head;
        ListNode slow = head;
        while ((fast != null) && (fast.next != null)) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //倒数第k个节点
    public ListNode daoShuForListNode(int k) {
        ListNode fast = head;
        ListNode slow = head;
        //fast先走k-1步
        k--;
        while ((k--) > 0) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode newNode = new ListNode(1);
        ListNode tmp = newNode;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tmp.next = head1;
                tmp = tmp.next;
                head1 = head1.next;
            } else {
                tmp.next = head2;
                tmp = tmp.next;
                head2 = head2.next;
            }
        }
        if (head1 == null) {
            tmp.next = head2;
        } else {
            tmp.next = head1;
        }
        return newNode.next;
    }

    public void printNode(ListNode node) {
        System.out.print(node.val);
    }

    //判断单链表是否是回文
    public boolean chkPalindrome(ListNode head) {
        //判空
        if (head == null) {
            return false;
        }
        //一个节点
        if (head.next == null) {
            return true;
        }
        //找到中间位置
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //逆置后半部分
        ListNode cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //判断
        while (head != slow) {
            //处理偶数的情况
            if(head.next==slow){
                return true;
            }
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;

    }
    public ListNode partition(ListNode head, int x) {
        // write code here
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        //定义两部分的头尾指针
        ListNode sb = null;
        ListNode sn = null;
        ListNode bb = null;
        ListNode bn = null;
        //开始遍历单链表
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                //第一次插入（尾插法的应用）
                if (sb == null) {
                   sb=new ListNode(cur.val);
                   sn=sb;
                } else {
                    sn.next =new ListNode(cur.val);
                    sn=sn.next;
                }

            } else {
                if (bb == null) {
                  bb=new ListNode(cur.val);
                  bn=bb;
                } else {
                    bn.next = new ListNode(cur.val);
                    bn=bn.next;
                }

            }
            cur = cur.next;
        }
        //如果全都是大于等于x的情况，直接返回bb，而不是sn.next==bb,会出现空指针异常
        if (sb != null) {
            sn.next = bb;
            return sb;
        }else{
            return bb;
        }


    }


    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        MySingleList mySingleList2 = new MySingleList();

////        mySingleList.creatList();
//        mySingleList.addLast(12);
//        mySingleList.addLast(45);
//        mySingleList.addLast(49);
//        mySingleList.addLast(78);
//        mySingleList.addLast(160);

        mySingleList2.addLast(8);
        mySingleList2.addLast(12);
        mySingleList2.addLast(5);
        mySingleList2.addLast(16);
        mySingleList2.addLast(1);
//        mySingleList.display(mySingleList.mergeTwoLists(mySingleList.head, mySingleList2.head));
        mySingleList.display(mySingleList2.partition(mySingleList2.head, 7));
//        mySingleList.display();
//        System.out.println();
//        mySingleList.display(mySingleList.reverseList());
//        mySingleList.display(mySingleList.middleNode());
//        mySingleList.printNode(mySingleList.daoShuForListNode(5));

//            mySingleList.display();
//            System.out.println();
//            mySingleList.addIndex(5, 250);
//            mySingleList.remove(7);
//            mySingleList.removeAllKey(12);
//            mySingleList.display();
//            System.out.println(mySingleList.size());
//            System.out.println(mySingleList.contains(116));

    }
}
